package com.justnow;

public class Solution1 {

    /**
     * 时间复杂度：O(N)，其中N是两颗树中节点个数的较小值
     * 空间复杂度：O(N),在最坏的情况下，会递归N层，需要O(N)的栈空间。
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        //如果当前两个节点都未null，那么只能返回一个null
        if (t1 == null && t2 == null)
            return null;
        //如果当前两个节点有一个为空，另一个不为空，那么返回其中不为空的节点。
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;

        //如果当前两个节点都不为空，那么将其中一个改为两个节点的值并重构树,返回该节点
        //合并两个根节点的值
        t1.val = t1.val + t2.val;
        // 合并后根节点的左子树应改为两个树的左子树合并后的结果。
        t1.left = mergeTrees(t1.left, t2.left);
        // 合并后根节点的右子树应该为两个树的右子树合并后的结果。
        t1.right = mergeTrees(t1.right, t2.right);
        // 返回根节点
        return t1;

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
